package cn.edu.jxau.test;

import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.concurrent.ExecutionException;

public class Main {

	public static void main(String[] args) throws InterruptedException, ExecutionException {

		Integer[] arr1 = new Integer[] { 1, 3, 5, 7, 9 };
		Integer[] arr2 = new Integer[] { 2, 4, 6, 8, 10 };
		Node<Integer> head1 = toLinkedList(arr1);
		Node<Integer> head2 = toLinkedList(arr2);
		print(merge(head1, head2));
	}

	private static <T extends Comparable<T>> Node<T> merge(Node<T> head1, Node<T> head2) {

		if (head1 == null && head2 == null) {
			throw new IllegalArgumentException("参数异常，两个都为空链表");
		} else if (head1 == null) {
			return head2;
		} else if (head2 == null) {
			return head1;
		}
		Node<T> head = null;
		if (head1.data.compareTo(head2.data) < 0) {
			head = head1;
			head.next = merge(head1.next, head2);
		} else {
			head = head2;
			head.next = merge(head1, head2.next);
		}
		return head;
	}

	private static <T> void print(Node<T> head) {

		Node<T> cur = head;
		while (cur != null) {
			System.out.print(cur.data + "\t");
			cur = cur.next;
		}
	}

	private static <T> Node<T> toLinkedList(T[] arr) {

		Objects.requireNonNull(arr, "参数arr不能为null");
		if (arr.length == 0) {
			return null;
		}

		Node<T> head = new Node<>(arr[0]);
		Node<T> cur = head;
		for (int i = 1; i < arr.length; i++) {
			Node<T> node = new Node<>(arr[i]);
			cur.next = node;
			cur = node;
		}
		return head;
	}
}

class Node<T> {

	public T data;
	public Node<T> next;

	public Node() {

	}

	public Node(T data) {
		this.data = data;
	}
}